package offer;

import java.util.Stack;

@FunctionalInterface
public interface BstFromPreorder {
    /**
     * 给定一个 BST 的前序遍历序列，构造出一个合法的 BST
     * @param preorder
     * @return
     */
    TreeNode bstFromPreorder(int[] preorder);
}

class BstFromPreorderImpl1 implements BstFromPreorder{

    /**
     * 时间复杂度o(n), 每个元素至多访问两次，第一次考虑其在其左侧插入，第二次考虑在其右侧插入
     * 空间复杂度o(n),最差情况是一个递减序列，此时BST可以退化为一个线性表，当处理到第n个元素时，前n - 1个元素在栈内。
     * BST 的中序遍历具有非减性质
     * 用两个栈，一个栈保存当前元素，另一个栈保存当前元素的父元素，
     * 如果一个新插入元素是当前元素的子元素，它需要小于当前等于当前元素，或者大于当前元素，但是小于等于当前元素的父元素
     * 若当前元素是根节点，则当前元素没有父元素，插入根节点右侧，并把根节点置为当前元素
     * @param preorder
     * @return
     */
    @Override
    public TreeNode bstFromPreorder(int[] preorder) {

        // 平凡情况
        if(preorder.length == 0){
            return null;
        }else if( preorder.length == 1){
            return new TreeNode(preorder[0]);
        }

        // 非平凡情况
        Stack<TreeNode> stack = new Stack<>();
        // root是处理时考虑的根，ans是preorder[0]，因为先序遍历第一个元素肯定是根，ans用于返回整棵树
        TreeNode root = new TreeNode(preorder[0]);
        TreeNode ans = root;
        stack.push(root);
        int cur = 1;
        int n = preorder.length;
        while(cur < n){
            TreeNode newNode = new TreeNode(preorder[cur]);
            while(true) {
                if (stack.size() == 1) {
                    // 根节点特殊处理
                    root = stack.pop();
                    if (newNode.val <= root.val) {
                        // 如果新节点小于等于根，插入根的左侧
                        root.left = newNode;
                        stack.push(root);
                        stack.push(newNode);
                    } else {
                        // 如果新节点大于根，插入根的右侧，将新节点置为根
                        root.right = newNode;
                        stack.push(newNode);
                    }
                    break;
                }else{
                    TreeNode curNode = stack.pop();
                    if(newNode.val <= curNode.val){
                        curNode.left = newNode;
                        stack.push(curNode);
                        stack.push(newNode);
                        break;
                    }else{
                        TreeNode preNode = stack.pop();
                        if(newNode.val <= preNode.val){
                            // curNode右侧已有元素，所以它不能在插入了
                            curNode.right = newNode;
                            stack.push(preNode);
                            stack.push(newNode);
                            break;
                        }else{
                            // 该层无法处理，需要考虑上一层
                            stack.push(preNode);
                        }
                    }
                }
            }
            cur++;
        }
        return ans;
    }
}
